package com.zj.leetcode.medium.stack;

import java.util.Stack;

/**
 * @program: algorithm
 * @description: 字符串解码
 * 394 decode-string
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class DecodeString {
    public static void main(String[] args) {
//        String s = "3[a]2[bc]qwe";
        String s = "3[a2[c]]";

        Solution solution = new DecodeString().new Solution();
        System.out.println(solution.decodeString(s));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String decodeString(String s) {


            int size = s.length();
            StringBuilder ret = new StringBuilder();



//            int quick = 0;
//            int slow = 0;
//            int num = 0;
//            boolean flag = false;
//            while (quick < size) {
//
//                if (Character.isDigit(s.charAt(quick))) {
//                    num = num * 10 + Character.getNumericValue(s.charAt(quick));
//                }
//
//                if (s.charAt(quick) == '[') {
//                    slow = quick + 1;
//                    flag = true;
//                }
//
//                if (s.charAt(quick) == ']') {
//                    while (num > 0) {
//                        ret.append(s, slow, quick);
//                        num--;
//                    }
//                    flag = false;
//                }
//
//                if (!flag && Character.isLowerCase(s.charAt(quick))) {
//                    ret.append(s.charAt(quick));
//                }
//
//                quick++;
//            }
            return ret.toString();
        }


        public String decodeString01(String s) {
            Stack<Integer> numStack = new Stack<>();
            Stack<Character> charStack = new Stack<>();

            int i, j, k;
            for (i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch - '0' >= 0 && ch - '0' <= 9) {
                    int nn = 0;
                    for (k = i; k < s.length(); k++) {
                        if (s.charAt(k) != '[') {
                            nn = nn * 10 + (s.charAt(k) - '0');
                        } else {
                            break;
                        }
                    }
                    numStack.push(nn);
                    i = k - 1;
                } else if (ch == ']') {
                    int num = numStack.pop();
                    StringBuilder tmp = new StringBuilder();
                    StringBuilder sb = new StringBuilder();
                    while (!charStack.isEmpty() && charStack.peek() != '[') {
                        tmp.append(charStack.pop());
                    }
                    tmp.reverse();
                    while (num > 0) {
                        sb.append(tmp);
                        num--;
                    }
                    charStack.pop();
                    for (j = 0; j < sb.length(); j++) {
                        charStack.push(sb.charAt(j));
                    }
                } else {
                    charStack.push(ch);
                }
            }

            StringBuilder sb = new StringBuilder();
            while (!charStack.isEmpty()) {
                if (charStack.peek() != '[') {
                    sb.append(charStack.pop());
                } else {
                    charStack.pop();
                }
            }

            return sb.reverse().toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
